package com.cn.codebrush.leetcode.editor.cn;

//给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。 
//
// 整数 a 比整数 b 更接近 x 需要满足： 
//
// 
// |a - x| < |b - x| 或者 
// |a - x| == |b - x| 且 a < b 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [1,2,3,4,5], k = 4, x = 3
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//输入：arr = [1,2,3,4,5], k = 4, x = -1
//输出：[1,2,3,4]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= arr.length 
// 1 <= arr.length <= 104 
// arr 按 升序 排列 
// -104 <= arr[i], x <= 104 
// 
// Related Topics 数组 双指针 二分查找 排序 堆（优先队列） 
// 👍 404 👎 0


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FindKClosestElements{

public static void main(String[] args) {

Solution solution = new FindKClosestElements().new Solution();
   int[] arr = {1,2,3,4,5};
   int k = 4;
   int x = 3;
System.out.println(solution.findClosestElements(arr,k,x));
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int n = arr.length;
        List<Integer> resList = new ArrayList<>();
        int right = n-1;
        int left = 0;
        int removeNum = n-k;
        while(removeNum>0){
            if(x-arr[left] <= arr[right]-x){
                right--;
            }else {
                left++;
            }

            removeNum--;
        }

        for(int i=left;i<=right;i++){
            resList.add(arr[i]);
        }

        return resList;
    }
}
//leetcode submit region end(Prohibit modification and deletion)























}